#include <vector>
using namespace std;
#include <iostream>


//version 1
class Solution {
public:
    using VINT = vector<int>;
    void MergeSortAndCountSmaller(VINT& ntmp, VINT& itmp, int left, int right, VINT& nums, VINT& index, VINT& ret) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;

        //[left, mid] [mid + 1, right]
        MergeSortAndCountSmaller(ntmp, itmp, left, mid, nums, index, ret);
        MergeSortAndCountSmaller(ntmp, itmp, mid + 1, right, nums, index, ret);

        //进入主逻辑
        int cur1 = left, cur2 = mid + 1, i = left;
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] > nums[cur2]) {
                //1.先算出来当前子数组下，cur1对应下标应该加多少值 -> 获取下标并 += (right - cur2 + 1)
                ret[index[cur1]] += (right - cur2 + 1);
                //index数组和nums数组需要绑定地移动！
                ntmp[i] = nums[cur1];
                itmp[i++] = index[cur1++];
            }
            else {
                ntmp[i] = nums[cur2];
                itmp[i++] = index[cur2++];
            }
        }
        while (cur1 <= mid) {
            ntmp[i] = nums[cur1];
            itmp[i++] = index[cur1++];
        }
        while (cur2 <= right) {
            ntmp[i] = nums[cur2];
            itmp[i++] = index[cur2++];
        }

        //把辅助数组返回到真实数组
        for (int j = left; j < i; ++j) {
            nums[j] = ntmp[j];
            index[j] = itmp[j];
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        //思路：把左右区间排成降序的区间，然后在主逻辑上：
        //左边数组需要两个部分，右边不需要！
        VINT ntmp(nums.size()), itmp(nums.size()), index(nums.size()), ret(nums.size());
        for (int i = 0; i < index.size(); ++i) index[i] = i;

        MergeSortAndCountSmaller(ntmp, itmp, 0, nums.size() - 1, nums, index, ret);
        return ret;
    }
};

int main() {
    //vector<int> v = getArrayWith200Inversions();
    vector<int> v1 = {0,2,1};
    vector<int> v = Solution().countSmaller(v1);
    for (auto x : v) {
        cout << x << " ";
    }
    cout << endl;
}
